public class code01s {
//    力扣 150 组合总和
public List<List<Integer>> combinationSum(int[] candidates, int target) {
    // 解法二：进行剪枝对递归进行处理

    // 同样的，起手先来创建一下返回列表
    // 以及存储当前值的列表
    List<List<Integer>> re = new ArrayList<>();
    List<Integer> adds = new ArrayList<>();

    // 首先针对特殊情况进行处理
    if(candidates.length == 0) {
        return re;
    }

    // 这里要先针对 candidates 进行一下排序曹组
    Arrays.sort(candidates);
    // 实现一下剪枝的回溯方法
    backtrack(re, adds, candidates, target, 0);

    return re;
}

    // 实现回溯方法
    // 简单说明一下这里的参数情况
    // 返回列表、局部合理数据列表
    // 数组信息
    // 目标值
    // 起始点(下标信息)
    private void backtrack(List<List<Integer>> re, List<Integer> adds, int[] candidates, int target, int start){
        // 这里是将 target 值与合适的数组元素进行递减进行操作的
        // 所以这里的判断条件是 target 值是否为 0
        if(target == 0) {
            // 此时表明已经找到的了合适的值，直接将元素添加进去即可
            re.add(new ArrayList<>(adds));
            return;
        }

        // 遍历数组
        // 从 start 开始遍历，进行剪枝排除重复子集的情况
        for(int i = start; i < candidates.length; i++) {
            // 如果子集的和超过 target ，此时就直接结束循环
            if(target - candidates[i] < 0) {
                break;
            }

            // 做出选择，将当前的值加入到 adds 数组中
            // 并且更新 target 目标值
            adds.add(candidates[i]);
            backtrack(re, adds, candidates, target - candidates[i], i);
            // 进行回退操作，撤销选择，清空 adds 数组
            adds.remove(adds.size() - 1);
        }
    }
}
